package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-27 15:41
 * @description: Functions of this class is
 *官方题解：
 * class Solution {
 *     int maxSum = Integer.MIN_VALUE;
 *
 *     public int maxPathSum(TreeNode root) {
 *         maxGain(root);
 *         return maxSum;
 *     }
 *
 *     public int maxGain(TreeNode node) {
 *         if (node == null) {
 *             return 0;
 *         }
 *
 *         // 递归计算左右子节点的最大贡献值
 *         // 只有在最大贡献值大于 0 时，才会选取对应子节点
 *         int leftGain = Math.max(maxGain(node.left), 0);
 *         int rightGain = Math.max(maxGain(node.right), 0);
 *
 *         // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
 *         int priceNewpath = node.val + leftGain + rightGain;
 *
 *         // 更新答案
 *         maxSum = Math.max(maxSum, priceNewpath);
 *
 *         // 返回节点的最大贡献值
 *         return node.val + Math.max(leftGain, rightGain);
 *     }
 * }
 **/
public class NoNo二叉树的最大路径和联系二叉树最大直径{
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    public static void main(String[] args) {

    }

    private int ans = Integer.MIN_VALUE;//设定变量存取答案

    public int maxPathSum(TreeNode root) {
        findMaxPath(root);
        return ans;
    }

    /**
     * 函数的作用：
     * 空节点的最大贡献值等于 0.
     * 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。
     *
     * 子树内部的最大路径和一定为：左边路径的最大值+右边路径的最大值+当前节点
     */
    private int findMaxPath(TreeNode root) {

        if (root != null) {
            //先进行递归，一直往下，直到走到根节点，然后往上回溯return的时候，计算当前节点的最大贡献值，
            //同时记录ans最大路径和的答案，将左节点的贡献值+右节点的最大贡献值+当前节点的值，即为答案
            int leftPointMaxGive = Math.max(findMaxPath(root.left), 0);//从左节点开始一直递归向下找寻最大的贡献值，只有当节点的贡献值>0的时候，才能被加入到路径中
            int rightPointMaxGive = Math.max(findMaxPath(root.right), 0);//同左节点一样的道理

            int tempPath = leftPointMaxGive + rightPointMaxGive + root.val;//子树内部的最大路径和为：左边路径的最大贡献值+右边路径的最大贡献值+当前节点的值
            ans = Math.max(tempPath , ans);//递归过程中，每次记录答案的值

            return root.val + Math.max(leftPointMaxGive, rightPointMaxGive);//返回当前路径的最大值
        }
        return 0;
    }
}